"""
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

 

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：

输入：nums = [1]
输出：1
示例 3：

输入：nums = [0]
输出：0
示例 4：

输入：nums = [-1]
输出：-1
示例 5：

输入：nums = [-100000]
输出：-100000
 

提示：

1 <= nums.length <= 3 * 104
-105 <= nums[i] <= 105
"""
from typing import List
class SolutionV1:
    def maxSubArray(self, nums: List[int]) -> int:
        funArr = [0 for i in range(len(nums))]
        for i in range(len(nums)):
            if nums[i] + funArr[i-1] > nums[i]:
                funArr[i] = nums[i] + funArr[i-1] 
            else:
                funArr[i] = nums[i]
        return max(funArr)


class SolutionV2:
    def maxSubArray(self, nums: List[int]) -> int:
        sum = nums[0]
        funArr = [0 for i in range(len(nums))]
        for i in range(len(nums)):
            if nums[i] + funArr[i-1] > nums[i]:
                funArr[i] = nums[i] + funArr[i-1] 
            else:
                funArr[i] = nums[i]
            if funArr[i] > sum:
                sum = funArr[i]
        return sum


class SolutionV3:
    def maxSubArray(self, nums: List[int]) -> int:
        return self.get_sum(nums,0, len(nums))

    @staticmethod
    def get_sum(nums:List[int], start:int, end:int) -> int:
        pass







if __name__ == '__main__':
    print(SolutionV2().maxSubArray([-2,1,-3,4,-1,2,1,-5,4]))
    print(SolutionV1().maxSubArray([-2,1,-3,4,-1,2,1,-5,4]))